The present invention generally relates to an arbitration method for a crossbar cell switch. More particularly, the present invention relates to a method for arbitrating among crossbar cell switch input queues to select the data to be sent to an output port during a particular switching epoch.
A crossbar switch is a switch that has, conceptually, a set of input (horizontal) paths, a set of output (vertical) paths, and a set of crosspoint switches or crosspoint elements, for interconnecting any one of the vertical paths to any one of the horizontal paths. Crossbar switches may be used in communications applications to provide switching for data or information packets, including Asynchronous Transfer Mode (ATM) cells. ATM cells are 53 bytes in size and are partitioned into a 5-byte header field and a 48-byte information field. When a crossbar switch is used to switch cell-based data traffic, such as ATM traffic, the crossbar switch may be referred to as a crossbar cell switch. The cells switched by the crossbar cell switch may be referred to alternatively as packets or data traffic. The period of time for a cell to be switched from its input port to any output port may be referred to alternatively as a switching epoch or a cell transfer epoch.
Crossbar cell switches may be used in a wide variety of communications applications. For example, whenever cells are received via more than one input port (horizontal path) and the communications traffic from any input needs to be directed to one of multiple output ports (vertical path), a crossbar cell switch may be used. Crossbar cell switches may be used in data switching fabrics including fiber optic or other network hubs, for example.
While many applications for crossbar cell switches exist throughout the communications field, certain design goals are universal. For example, arbitration between input ports is preferably simple and fast to accommodate the high speed cell switching typical of modern cell switching fabrics such as ATM (Asynchronous Transfer Mode) cell switching fabrics. In the past, however, crossbar cell switches have fallen short of these goals.
In typical crossbar cell switches, only one cell may be transferred to a given output port during each cell transfer (switching) epoch. Since two or more input ports may each concurrently have a cell directed to a specific output port, a crossbar cell switch must arbitrate between input ports for service during the current cell transfer (switching) epoch. In other words, the crossbar cell switch must determine which input port may send data to a particular output port during the current cell transfer epoch.
Furthermore, each input port is preferably associated with a buffer to hold cells that cannot be transferred during the current cell transfer epoch. Typically, this buffer forms a first-in-first-out (FIFO) queue at each input port. The cell at the head of the queue at each port is referred to as the xe2x80x9chead of linexe2x80x9d cell (HoL). Any cell in the queue, including the HoL cell, may be destined to any output port.
In the past, arbitration methods assigned the cell transfer opportunity (which HoL cell to switch) for a given output port for the current cell transfer epoch to the first encountered HoL cell directed to that output. For instance, the cell transfer opportunity for output j for the current cell transfer epoch was assigned by examining, in consecutive order, the HoL cells at each input queue and selecting the first HoL cell directed to output j.
This approach, which consistently gives first opportunities to input port with low index, may be categorized as xe2x80x9cunfair.xe2x80x9d Additionally, other techniques, including examining the input ports in round robin (cyclic) order were used in the past. In a cyclic technique, the HoL cells at each input queue are examined in sequence beginning with a different, sequential, input port each time. Cyclic techniques attempted to achieve xe2x80x9cfairnessxe2x80x9d (i.e., to prevent a single input port from monopolizing transfer resources.)
After selection of the HoL cell to be transferred to output port j during the current cell transfer epoch, other HoL cells directed to output j are blocked and cannot be transferred during the current cell transfer epoch. Additionally, the cells in each queue following the blocked HoL cells are also blocked because only an HoL cell may be transferred to an output port.
Further examination of the crossbar cell switch operating under existing arbitration methods reveals that if, for instance, the HoL cells of multiple input ports are directed towards the same output port j, a delay of one switching epoch per input port directed to output port j results before all the HoL cells have been switched to the output port j. During this delay, additional cells may arrive at any of the input ports, but must wait until the HoL cell has been switched (transferred) before the new cells (or any other cells higher in the queue) may be considered; this is often termed head of line cell blocking. If the delay in transfer is sufficiently long, cells arriving at an input port overrun that input port""s queue and the incoming cell is lost.
This HoL cell blocking phenomenon may result in saturation (i.e., the queue sizes at the input ports grow without bound) when the average transfer load (cells switched per transfer epoch) reaches a certain level. That is, when the crossbar cell switch must transfer a certain average number of cells per cell transfer epoch per input port greater than its saturation threshold, the crossbar cell switch cannot meet the demand and the input port queues grow without bound. The threshold point for saturation may vary based on the type of crossbar cell switch and the system in which it is used. The upper bound on saturation is 1.0 cells per transfer epoch per input port. Generally, switching 1.0 cells per transfer epoch per input port is an unachievable goal in a crossbar cell switch. Theoretical analysis of round robin and other fair arbitration shows that a crossbar cell switch with fair arbitration will saturate when the average cell transfer rate approaches 0.58 cells per switch epoch at any input port.
In operation, an input port may be loaded to 100 percent, during peak loading conditions, so that one cell arrives per input epoch over an extended interval. Saturation may be avoided if the duration of a switch epoch is less than the duration of an input epoch so that, on average, more than one switching opportunity exists for each arriving cell. Alternately, the cycle rate at which switch transfers occur may be higher than the cycle rate at which cells arrive at the input ports.
The ratio of the rate at which switch transfer opportunities (i.e., cycles) occur to the maximum rate at which cells arrive at the input ports is known as the overspeed ratio. For typical fair arbitration methods, the overspeed ratio must be at least 1/0.58 (or about 1.70) to ensure that an input port may handle a peak load without entering saturation. Also, in a typical system, the overspeed ratio is even higher than 1.70 so that the likelihood of a large input queue is minimized.
In yet another know arbitration method, the cyclic examination of input ports start with the input port currently having the largest queue. This arbitration method results in lower input queue occupancy than does the round-robin start referred to previously. However, this arbitration method also experiences saturation at approximately 0.58 cells per switch epoch which seems to be a performance limit on all fair arbitration methods, including the present invention.
The basic performance of a crossbar cell switch is discussed in xe2x80x9cPerformance Analysis of Nonblocking Packet Switch with Input and Output Buffers,xe2x80x9d Oie, Murata, Kubota, Miyahara, IEEE Transactions on Communications, Vol. 40, No. 8, August 1992 (hereafter Oie). Oie discloses a non-blocking packet switch with input buffers, however, Oie does not address arbitration techniques for improving the performance of crossbar cell switches.
Thus, a need exists for an improved crossbar cell switch arbitration method able to switch a greater number of data cells per switching epoch to provide a higher saturation threshold and/or a reduced minimum overspeed ratio.
One object of the present invention is to provide crossbar cell switch and a queue arbitration method to provide more efficient switching between input and output ports.
Another object of the present invention is to provide an improved crossbar cell switch arbitration method based on the size of the input port queues of the subset of input ports whose Head of Line (HoL) cells are addressed to a common output port.
Another object of the present invention is to provide an improved crossbar cell switch arbitration method which permits a lower overspeed ratio to support a given input load, subject to the theoretical saturation limit for a crossbar switch. A lower overspeed ratio results in lower power required to operate the cell switch, which is particularly beneficial in a satellite-based switch.
Another object of the present invention is to provide an improved crossbar cell switch arbitration method which allows for smaller queue sizes for a given overspeed ratio. Reducing the size of the input queues reduces switching delays and permits the input buffer size to be reduced providing a reduction in the overall weight of the crossbar cell switch which may, in turn, significantly reduce switch manufacturing and installation costs, particularly when the crossbar cell switch is used in a satellite-based system.
Another objective of the present invention is to provide an improved crossbar cell switch which minimizes the maximum input queue size. Longer input queues result in longer buffer delays which may increase Cell Delay Variation (CDV). Decreasing CDV provides higher data throughput quality of service by minimizing fluctuations in propagation delays through the switch.
Another objective of the present invention is to provide an improved crossbar cell switch which permits a simple queue size comparison based on the most significant bit of the queue size. The queue size comparison may also be based on the index of the most significant bit of the queue size when expressed in binary form, or equivalently the integer portion of the binary logarithm of the queue size. Reducing the number of bits to be considered at each comparator in the switch may provide for faster arbitration while educing the overall weight of the crossbar cell switch.
Another objective of the present invention is to provide an improved crossbar cell switch which permits a simple architecture and logic structure for the crosspoint element of the crossbar cell switch.
Another objective of the present invention is to provide an improved crossbar cell switch which permits a xe2x80x9cfairxe2x80x9d treatment of all input ports in that no input port may monopolize any output port to the exclusion of all other input ports.
Another objective of the present invention is to provide an improved crossbar cell switch which uses a logic tree for fast arbitration among multiple input ports having HoL cells addressed to a common output port.
Another objective of the present invention is to provide an improved crossbar cell switch in which the arbitration and data transfer periods proceed in parallel, lowering the overall time for each switching epoch and improving the overspeed ratio.
One or more of the foregoing objects are met in whole or in part by an improved arbitration method and apparatus for a crossbar cell switch.
In the crossbar cell switch the input ports have buffers that hold queues of cells awaiting transfer to an output port. The first cell of each non-empty queue is known as the Head of Line (HoL) cell. The arbitration method includes identifying input queues having HoL cells directed to a predetermined output port, comparing the sizes of said input queues, responsively generating a queue select signal, and switching a HoL cell from an associated input queue to an output port in response to said queue select signal. The comparison of the sizes of the input queues returns the input queue with the greatest size. The comparison may also be performed on, for example, the binary logarithms of the queue sizes, or on the integer portion of the binary logarithm of the queue sizes which may be equivalent to the index of the most significant bit of the queue size expressed in binary notation. The switching step of the current switching epoch may proceed in parallel with the identifying and comparing steps of the next subsequent switching epoch.
These and other features of the present invention re discussed or apparent in the following detailed description of the preferred embodiments of the invention.